home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 1 Issue 2 / PDCD-1 - Issue 02.iso / _utilities / utilities / 003 / _gs / !GS / c / IDICT < prev    next >
Text File  |  1991-10-26  |  11KB  |  362 lines
  1. /* Copyright (C) 1989, 1990, 1991 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* idict.c */
  21. /* Dictionaries for Ghostscript */
  22. #include "ghost.h"
  23. #include "alloc.h"
  24. #include "errors.h"
  25. #include "name.h"
  26. #include "save.h"            /* for value cache in names */
  27. #include "store.h"
  28. #include "dict.h"    /* interface definition */
  29.  
  30. /* Imported procedures */
  31. extern int obj_eq(P2(ref *, ref *));
  32.  
  33. /*
  34.  * A dictionary is a structure of two elements (refs).
  35.  * The first element is a t_integer whose value says how many
  36.  * entries are occupied (N).  The second element is a t_array
  37.  * of 2N+2 elements, containing alternating keys and values.
  38.  * Unused entries have null as the key.  The first entry also
  39.  * has null as the key (to avoid a special wrap-around check).
  40.  * For now, deleted entries have an executable null as the key:
  41.  * this degrades lookup time as entries are inserted and deleted,
  42.  * and will probably have to be changed someday.
  43.  * The access attributes for the dictionary are stored in
  44.  * the contents ref.
  45.  */
  46. struct dict_s {
  47.     ref count;            /* t_integer */
  48.     ref contents;            /* t_array */
  49. };
  50. struct pair_s {
  51.     ref key;
  52.     ref value;
  53. };
  54. typedef struct pair_s pair;
  55. #define pairs(dct) (pair *)((dct)->contents.value.refs)
  56. #define npairs(dct) ((r_size(&(dct)->contents) >> 1) - 1)
  57.  
  58. /* Define the size of the largest valid dictionary. */
  59. /* This is limited by the size field of the contents ref. */
  60. uint dict_max_size = max_ushort / 2 - 1;
  61.  
  62. /* Create a dictionary. */
  63. int
  64. dict_create(uint size, ref *pref)
  65. {    uint asize = (size == 0 ? 1 : size) + 1;
  66.     dict *pdict =
  67.       (dict *)alloc_refs(sizeof(dict) / sizeof(ref), "dict_create");
  68.     pair *pp;
  69.     if ( pdict == 0 ) return e_VMerror;
  70.     pp = (pair *)alloc_refs(asize * 2, "dict_create(pairs)");
  71.     if ( pp == 0 )
  72.        {    alloc_free((char *)pdict, 1, sizeof(dict), "dict_create");
  73.         return e_VMerror;
  74.        }
  75.     make_tv_new(&pdict->count, t_integer, intval, 0);
  76.     make_tasv_new(&pdict->contents, t_array, a_all, asize * 2,
  77.               refs, (ref *)pp);
  78.     make_tav_new(pref, t_dictionary, a_all, pdict, pdict);
  79.     pp = pairs(pdict);
  80.     while ( asize-- )
  81.         make_null_new(&pp->key),
  82.         make_null_new(&pp->value),
  83.         pp++;
  84.     return 0;
  85.    }
  86.  
  87. /*
  88.  * Return a pointer to a ref that holds the access attributes
  89.  * for a dictionary.
  90.  */
  91. ref *
  92. dict_access_ref(ref *pdref)
  93. {    return &pdref->value.pdict->contents;
  94. }
  95.  
  96. /*
  97.  * Look up in a stack of dictionaries.  Store a pointer to the value slot
  98.  * where found, or to the (value) slot for inserting.
  99.  * Return 1 if found, 0 if not and there is room for a new entry in
  100.  * the top dictionary on the stack, or e_dictfull if the top dictionary
  101.  * is full and the key is missing.
  102.  * Note that pdbot <= pdtop, and the search starts at pdtop.
  103.  */
  104. int
  105. dict_lookup(ref *pdbot, ref *pdtop, ref *pkey,
  106.   ref **ppvalue /* result is stored here */)
  107. {    ref *pdref = pdtop;
  108.     uint hash;
  109.     int ktype;
  110.     name *kpname;
  111.     int full = 1;            /* gets set to 0 or e_dictfull */
  112.     pair *pslot = 0;
  113.     /* Compute hash.  The only types we bother with are strings, */
  114.     /* names, and (unlikely, but worth checking for) integers. */
  115.     switch ( r_type(pkey) )
  116.        {
  117.     case t_name:
  118.         kpname = pkey->value.pname;
  119. nh:        hash = kpname->index * 40503;
  120.         ktype = t_name;
  121.         break;
  122.     case t_string:            /* convert to a name first */
  123.        {    ref nref;
  124.         int code = name_ref(pkey->value.bytes,
  125.                     r_size(pkey), &nref, 1);
  126.         if ( code < 0 ) return code;
  127.         kpname = nref.value.pname;
  128.        }    goto nh;
  129.     case t_integer:
  130.         hash = (uint)pkey->value.intval * 40503;
  131.         ktype = -1;
  132.         break;
  133.     default:
  134.         hash = r_btype(pkey) * 99;    /* yech */
  135.         ktype = -1;
  136.        }
  137.     do
  138.        {    dict *pdict = pdref->value.pdict;
  139.         uint size = npairs(pdict);
  140.         pair *ppbot = pairs(pdict);
  141.         register pair *pp;        /* probe pointer */
  142.         int wrap = 0;
  143.         register int etype;
  144.         /* Search the dictionary */
  145. #ifdef DEBUG
  146. if ( gs_debug['d'] )
  147.            {    extern void debug_print_ref(P1(ref *));
  148.             dprintf("[d]");
  149.             debug_print_ref(pdref);
  150.             dprintf(":");
  151.             debug_print_ref(pkey);
  152.             dprintf("->");
  153.            }
  154. #endif
  155. #ifdef DEBUG
  156. #  define print_found()\
  157. if ( gs_debug['d'] )\
  158.    {    extern void debug_print_ref(P1(ref *));\
  159.     debug_print_ref(&pp->value);\
  160.     dprintf("; ");\
  161.    }
  162. #else
  163. #  define print_found()
  164. #endif
  165.         for ( pp = ppbot + (hash % size) + 2; ; )
  166.            {    if ( (etype = r_type(&(--pp)->key)) == ktype )
  167.                {    /* Fast comparison if both keys are names */
  168.                 if ( pp->key.value.pname == kpname )
  169.                    {    *ppvalue = &pp->value;
  170.                     print_found();
  171.                     return 1;
  172.                    }
  173.                }
  174.             else if ( etype == t_null )
  175.                {    if ( r_has_attrs(&pp->key, a_executable) )
  176.                    {    /* Deleted entry, save the slot. */
  177.                     if ( pslot == 0 ) pslot = pp;
  178.                    }
  179.                 /* We might have hit the dummy entry at */
  180.                 /* the beginning, in which case we should */
  181.                 /* wrap around to the end. */
  182.                 else if ( pp == ppbot )    /* wrap */
  183.                    {    if ( wrap++ )    /* wrapped twice */
  184.                        {    if ( full > 0 )
  185.                            {    if ( pslot != 0 )
  186.                                 break;
  187.                             full = e_dictfull;
  188.                            }
  189.                         goto next_dict;
  190.                        }
  191.                     pp += size + 1;
  192.                    }
  193.                 else    /* key not found */
  194.                     break;
  195.                }
  196.             else
  197.                {    if ( obj_eq(&pp->key, pkey) )
  198.                    {    *ppvalue = &pp->value;
  199.                     print_found();
  200.                     return 1;
  201.                    }
  202.                }
  203.            }
  204.         if ( full > 0 )
  205.            {    *ppvalue = (pslot != 0 ? &pslot->value : &pp->value);
  206. #ifdef DEBUG
  207. if ( gs_debug['d'] )
  208.             dprintf1("0(%lx); ", (ulong)*ppvalue);
  209. #endif
  210.             full = 0;
  211.            }
  212. next_dict: ;
  213.        }
  214.     while ( --pdref >= pdbot );
  215.     return full;
  216. }
  217.  
  218. /*
  219.  * Enter a key-value pair in a dictionary.
  220.  * The caller is responsible for ensuring key is not a null.
  221.  * Return 0, e_dictfull, or e_VMerror if the key was a string
  222.  * and a VMerror occurred when converting it to a name.
  223.  */
  224. int
  225. dict_put(ref *pdref /* t_dictionary */, ref *pkey, ref *pvalue)
  226. {    ref *pvslot;
  227.     if ( dict_find(pdref, pkey, &pvslot) <= 0 )    /* not found */
  228.        {    /* Check for overflow */
  229.         dict *pdict = pdref->value.pdict;
  230.         ref kname;
  231.         if ( pdict->count.value.intval == npairs(pdict) )
  232.             return e_dictfull;
  233.         /* If the key is a string, convert it to a name. */
  234.         if ( r_has_type(pkey, t_string) )
  235.            {    int code = name_from_string(pkey, &kname);
  236.             if ( code < 0 ) return code;
  237.             pkey = &kname;
  238.            }
  239.         ref_save(&pdict->count, "dict_put(count)");
  240.         pdict->count.value.intval++;
  241.         ref_assign_old(pvslot - 1, pkey, "dict_put(key)");    /* set key of pair */
  242.         /* If the key is a name, update its 1-element cache. */
  243.         if ( r_has_type(pkey, t_name) )
  244.            {    name *pname = pkey->value.pname;
  245.             if ( pname->pvalue == pv_no_defn &&
  246.                 (pdict == systemdict.value.pdict ||
  247.                  pdict == userdict.value.pdict) &&
  248.                 /* Only set the cache if we aren't inside */
  249.                 /* a save.  This way, we never have to */
  250.                 /* undo setting the cache. */
  251.                 alloc_save_level() == 0
  252.                )
  253.                {    /* Set the cache */
  254.                 pname->pvalue = pvslot;
  255.                }
  256.             else    /* The cache is worthless */
  257.                 pname->pvalue = pv_other;
  258.            }
  259.        }
  260.     ref_assign_old(pvslot, pvalue, "dict_put(value)");
  261.     return 0;
  262. }
  263.  
  264. /* Remove an element from a dictionary. */
  265. int
  266. dict_undef(ref *pdref, ref *pkey)
  267. {    ref *pvslot;
  268.     dict *pdict;
  269.     if ( dict_find(pdref, pkey, &pvslot) <= 0 )
  270.         return e_undefined;
  271.     /* Remove the entry from the dictionary. */
  272.     pdict = pdref->value.pdict;
  273.     pvslot--;            /* point to key, not value */
  274.     make_null_old(pvslot, "dict_undef(value)");
  275.     /* Accumulating deleted entries slows down lookup. */
  276.     /* Detect the easy case where we can use an empty entry */
  277.     /* rather than a deleted one, namely, when the next entry */
  278.     /* in the probe order is empty. */
  279.     if ( r_has_type(pvslot - 2, t_null) &&
  280.          !r_has_attrs(pvslot - 2, a_executable) &&
  281.          pvslot - 2 != pdict->contents.value.refs    /* not wraparound */
  282.         )
  283.         r_set_attrs(pvslot, a_executable);    /* mark as deleted */
  284.     ref_save(&pdict->count, "dict_undef(count)");
  285.     pdict->count.value.intval--;
  286.     /* If the key is a name, update its 1-element cache. */
  287.     if ( r_has_type(pkey, t_name) )
  288.        {    name *pname = pkey->value.pname;
  289.         if ( pv_valid(pname->pvalue) &&
  290.             (pdict == systemdict.value.pdict ||
  291.              pdict == userdict.value.pdict) )
  292.            {    /* Clear the cache */
  293.             pname->pvalue = pv_no_defn;
  294.            }
  295.        }
  296.     return 0;
  297. }
  298.  
  299. /* Return the number of elements in a dictionary. */
  300. uint
  301. dict_length(ref *pdref /* t_dictionary */)
  302. {    return (uint)(pdref->value.pdict->count.value.intval);
  303. }
  304.  
  305. /* Return the capacity of a dictionary. */
  306. uint
  307. dict_maxlength(ref *pdref /* t_dictionary */)
  308. {    return npairs(pdref->value.pdict);
  309. }
  310.  
  311. /* Copy one dictionary into another. */
  312. int
  313. dict_copy(ref *pdrfrom /* t_dictionary */, ref *pdrto /* t_dictionary */)
  314. {    dict *pdict = pdrfrom->value.pdict;
  315.     int count = npairs(pdict) + 1;    /* +1 for dummy first entry */
  316.     pair *pp = pairs(pdict);
  317.     int code;
  318.     for ( ; count--; pp++ )
  319.       if ( !r_has_type(&pp->key, t_null) )
  320.         if ( (code = dict_put(pdrto, &pp->key, &pp->value)) != 0 )
  321.           return code;
  322.     return 0;
  323. }
  324.  
  325. /* Resize a dictionary. */
  326. int
  327. dict_resize(ref *pdrfrom, uint new_size)
  328. {    dict *pdict = pdrfrom->value.pdict;
  329.     ref drto;
  330.     int code;
  331.     if ( (code = dict_create(new_size, &drto)) < 0 ) return code;
  332.     dict_copy(pdrfrom, &drto);    /* can't fail */
  333.     /* Free the old dictionary */
  334.     alloc_free((char *)pdict->contents.value.refs,
  335.            dict_maxlength(pdrfrom), sizeof(pair), "dict_resize(old)");
  336.     *pdict = *drto.value.pdict;
  337.     /* Free the new dictionary header */
  338.     alloc_free((char *)drto.value.pdict,
  339.            1, sizeof(dict), "dict_resize(new)");
  340.     return 0;
  341. }
  342.  
  343. /* Prepare to enumerate a dictionary. */
  344. int
  345. dict_first(ref *pdref)
  346. {    return (int)(npairs(pdref->value.pdict) + 1);    /* +1 for dummy */
  347. }
  348.  
  349. /* Enumerate the next element of a dictionary. */
  350. int
  351. dict_next(ref *pdref, int index, ref *eltp /* ref eltp[2] */)
  352. {    pair *pp = pairs(pdref->value.pdict) + index;
  353.     while ( pp--, --index >= 0 )
  354.        {    if ( !r_has_type(&pp->key, t_null) )
  355.            {    eltp[0] = pp->key;
  356.             eltp[1] = pp->value;
  357.             return index;
  358.            }
  359.        }
  360.     return -1;            /* no more elements */
  361. }
  362.